package arithmetic2.day02;

import java.util.Arrays;

/*
    由归并排序演变而来的问题:
    求数组的小和:
        1个元素的小和 = 某个元素的左边比这个元素小的数的和
        数组中所有元素的小和加起来等于数组的小和
 */
public class Demo01 {
    public static void main(String[] args) {
        int arr[] = new int[]{1, 3, 4, 2, 5};
        int result = mergeSort(arr, 0, arr.length - 1, new int[arr.length]);
        System.out.println(Arrays.toString(arr));
        System.out.println(result);
    }

    //归并排序
    public static int mergeSort(int arr[], int start, int end, int temp[]) {
        if (start < end) {
            int mid = (start + end) >> 1;
            //两个子序列分别排序
            int leftResult = mergeSort(arr, start, mid, temp);
            int rightResult = mergeSort(arr, mid + 1, end, temp);
            //将两个子序列合并
            return merge(arr, start, mid, end, temp) + leftResult + rightResult;
        }
        return 0;
    }

    //归并
    public static int merge(int arr[], int start, int mid, int end, int temp[]) {
        int result = 0;
        int i = start;
        int j = mid + 1;
        int k = start;
        while (i <= mid && j <= end) {
            result += arr[i] < arr[j] ? (end - j + 1) * arr[i] : 0;
            temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
        }
        while (i <= mid) {
            temp[k] = arr[i];
            i++;
            k++;
        }
        while (j <= end) {
            temp[k] = arr[j];
            j++;
            k++;
        }
        k = start;
        while (k <= end) {
            arr[k] = temp[k];
            k++;
        }
        return result;
    }
}
